/*
 * 0064. 合并排序数组
 * 合并两个排序的整数数组A和B变成一个新的数组。
 * https://www.lintcode.com/problem/merge-sorted-array/description
 * 
 * 样例
 * 给出 A = [1, 2, 3, empty, empty], B = [4, 5]
 * 合并之后 A 将变成 [1,2,3,4,5]
 * 
 * 2018.07.13 @jeyming
 */
package merge_sorted_array_0064;

public class Merge_sorted_array_0064 {
	/*
	 * @param A: sorted integer array A which has m elements, but size of A is m+n
	 * @param m: An integer
	 * @param B: sorted integer array B which has n elements
	 * @param n: An integer
	 * @return: nothing
	 */
	public void mergeSortedArray(int[] A, int m, int[] B, int n) {
		// write your code here
		if(m == 0) {
			for(int i = 0; i < n; ++i) {
				A[i] = B[i];
			}
		} else {
			if(n != 0) {
				if(A[m - 1] <= B[0]) {
					for(int i = 0; i < n; ++i) {
						A[m + i] = B[i];
					}
				} else if(A[0] >= B[n - 1]) {
					for(int i = m + n - 1, j = m - 1; j >= 0; --i, --j) {
						A[i] = A[j];
					}
					for(int i = 0; i < n; ++i) {
						A[i] = B[i];
					}
				} else {
					int[] number = new int[m + n];
					int cntA = 0;
					int cntB = 0;
					int cnt =0;
					while((cntA < m) || (cntB < n)) {
						if((cntA < m) && (cntB < n)) {
							if(A[cntA] > B[cntB]) {
								number[cnt++] = B[cntB];
								++cntB;
							} else if(A[cntA] < B[cntB]) {
								number[cnt++] = A[cntA];
								++cntA;
							} else if(A[cntA] == B[cntB]) {
								number[cnt++] = A[cntA];
								number[cnt++] = B[cntB];
								++cntA;
								++cntB;
							} 
						} else if((cntA < m) && (cntB >= n)) {
							number[cnt++] = A[cntA];
							++cntA;
						} else if((cntA >= m) && (cntB < n)) {
							number[cnt++] = B[cntB];
							++cntB;
						}
					}
					for(int i = 0; i < number.length; ++i) {
						A[i] = number[i];
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
